use num::BigUint;
pub fn min_edge_prime_num(number: u32) -> String {
    let mut iter = Iter::new(1 as u128, 0);
    while let Some(p) = iter.next() {
        if p * 100. < number as f64 {
            break;
        }
    }
    iter.to_string()
}

// 用来叠带边数和素数的个数
#[derive(Debug)]
struct Iter {
    edges: u128,       // 当前的边数，限制到u128类型的长度，超过长度，迭代器返回
    prime_count: u128, // 当前的素数个数
}

impl Iter {
    #[inline(always)]
    const fn new(edges: u128, prime_count: u128) -> Self {
        debug_assert!(edges % 2 != 0); // 必须是奇数
        Self { edges, prime_count }
    }
}

impl ToString for Iter {
    fn to_string(&self) -> String {
        format!("{},{}", self.edges, self.prime_count)
    }
}

impl Iterator for Iter {
    type Item = f64;

    // 叠带一次返回边数+1后的百分比,如果返回空，数据溢出了
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.edges = self.edges.checked_add(2)?; // 下一个边长,增加2，还是奇数
        let mut max_value = self.edges.checked_pow(2)?; // 下一个边的顶点最大值
        for _ in 1..4 {
            max_value = max_value - self.edges + 1; // 不用担心溢出
            if is_prime_u128(max_value) {
                self.prime_count += 1; // 素数个数毕竟很少，不用担心溢出
            }
        }

        // 素数的个数，除以对角线的个数
        let prime = self.prime_count as f64; // 很少
        let line = (2 * self.edges - 1) as f64; // 前面的u128没有溢出，这里的边数更不会溢出
        Some(prime / line)
    }
}

// ----------------------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------------------
// 下面是用到的判断是不是素数的算法，米勒拉宾算法
// 使用费马小定理进行快速检测的基数集合
static A: [u128; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];

// 米勒拉宾素性检验：如果n是一个素数的话，那么n-1可以写成n-1=(a的(2^r)*d次方)*d
// 0<= r <= s-1,a是随机的从[1, n-1]中选取的，如果我们能找到(a^d mod n) != 1 且 (a的(2^r)*d次方) mod n != -1
// 则说明a是n为合数的一个凭证。
// 参数解释:a,d，n分别是公式中的a,d,n
// 这个函数计算出a^d mod n的值。使用快速幂算法。
// 初始化结果为1，基数为a，指数为d。
// 当指数d大于0时，如果d为奇数，则将结果乘以基数并对n取模。
// 将基数平方并对n取模，将指数整除2。
// 重复上述步骤直到指数d为0。
// 返回a^d mod n
fn fast_power_mod_u128(mut a: u128, mut d: u128, n: u128) -> u128 {
    let mut res: u128 = 1;
    while d != 0 {
        if (d & 1) != 0 {
            res = overflow_handle(res, a, n);
        }
        a = overflow_handle(a, a, n);
        d >>= 1;
    }
    res
}

#[inline(always)]
fn overflow_handle(a: u128, b: u128, m: u128) -> u128 {
    if a.checked_mul(b).is_none() {
        let a: BigUint = a.into();
        let b: BigUint = b.into();
        let m: BigUint = m.into();
        let ret = (a * b % m).to_u64_digits();
        let len = ret.len();
        if len == 1 {
            ret[0] as u128
        } else if len == 2 {
            (ret[1] as u128) << 64 | (ret[0] as u128)
        } else {
            0
        }
    } else {
        a * b % m
    }
}

/// 米勒拉宾素性检验：如果n是一个素数的话，那么n-1可以写成n-1=(a的(2^r)*d次方)*d
/// 0<= r <= s-1,a是随机的从[1, n-1]中选取的，如果我们能找到(a^d mod n) != 1 且 (a的(2^r)*d次方) mod n != -1
/// 则说明a是n为合数的一个凭证。
/// 参数解释:a,d，n分别是公式中的a,d,n
pub fn is_prime_u128(n: u128) -> bool {
    if n < 3 || &n % 2 == 0 {
        return n == 2;
    }
    // t保存的是s的值
    let mut t = 0;
    let mut d = n - 1;
    while d % 2 == 0 {
        d = d / 2;
        t = t + 1;
    }

    for a in A {
        let mut v = fast_power_mod_u128(a, d, n);
        if v == 1 || v == n - 1 || v == 0 {
            continue;
        }
        let mut i = 1;

        while i <= t {
            v = overflow_handle(v, v, n);
            if v == n - 1 && i != t {
                v = 1; // 不需要再循环了。
                break;
            }
            if v == 1 {
                return false;
            }
            i = i + 1u8;
        }

        if v != 1 {
            return false;
        }
    }
    true
}
